package Queue_and_Stack;

/*
01 矩阵
给定一个由 0 和 1 组成的矩阵 mat，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]
示例 2：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/queue-stack/g7pyt/
 */

import java.util.*;

public class _55_01矩阵 {
    public static void main(String[] args) {

        int[][] ints = {{0,0,0},{0,1,0},{1,1,1}};
        int[][] mat = {{1,0,1,1,0,0,1,0,0,1},{0,1,1,0,1,0,1,0,1,1},{0,0,1,0,1,0,0,1,0,0},{1,0,1,0,1,1,1,1,1,1},{0,1,0,1,1,0,0,0,0,1},{0,0,1,0,1,1,1,0,1,0},{0,1,0,1,0,1,0,0,1,1},{1,0,0,0,1,1,1,1,0,1},{1,1,1,1,1,1,1,0,1,0},{1,1,1,1,0,1,0,0,1,1}};
        updateMatrix(mat);
        for (int i = 0; i < mat.length; i++) {
            for (int i1 = 0; i1 < mat[0].length; i1++) {
                System.out.print(mat[i][i1] + " ");
            }
            System.out.println();
        }

    }

    //BFS
    //超时
    public static int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        boolean flag = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    flag = false;
                    break;
                }
            }
        }
        if (flag) {
            return mat;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] != 0) {
                    int step = 1;
                    Deque<int[]> queue = new LinkedList<>();
                    int[][] newMat = new int[m][n];
                    queue.offer(new int[]{i, j});
                    newMat[i][j] = 1;
                    while(queue != null && !queue.isEmpty()){
                        int size = queue.size();
                        for (int i1 = 0; i1 < size; i1++) {
                            int[] poll = queue.poll();
                            int x = poll[0];
                            int y = poll[1];
                            if (change(mat,x,y,queue,newMat)){
                                queue = null;
                                mat[i][j] = step;
                                break;
                            }
                        }
                        step++;
                    }
                }
            }
        }
        return mat;
    }

    public  static boolean change(int[][] mat, int i, int j, Deque<int[]> queue,int[][] newmat) {
        int m = mat.length;
        int n = mat[0].length;
        int left = j - 1;
        int right = j + 1;
        int top = i - 1;
        int bottom = i + 1;
        if(left != -1) {
            if(mat[i][left] == 0){
                return true;
            }else {
                if(newmat[i][left] == 0){
                    queue.offer(new int[]{i, left});
                    newmat[i][left] = 1;
                }
            }
        }
        if(right != n) {
            if(mat[i][right] == 0){
                return true;
            }else {
                if(newmat[i][right] == 0){
                    queue.offer(new int[]{i, right});
                    newmat[i][right] = 1;
                }
            }
        }
        if(top != -1) {
            if(mat[top][j] == 0){
                return true;
            }else {
                if(newmat[top][j] == 0){
                    queue.offer(new int[]{top, j});
                    newmat[top][j] = 1;
                }
            }
        }
        if(bottom != m) {
            if(mat[bottom][j] == 0){
                return true;
            }else {
                if(newmat[bottom][j] == 0){
                    queue.offer(new int[]{bottom, j});
                    newmat[bottom][j] = 1;
                }
            }
        }
        return false;
    }

    //官解：BFS
    class Solution {
        static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        public int[][] updateMatrix(int[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            int[][] dist = new int[m][n];
            boolean[][] seen = new boolean[m][n];
            Queue<int[]> queue = new LinkedList<int[]>();
            // 将所有的 0 添加进初始队列中
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (matrix[i][j] == 0) {
                        queue.offer(new int[]{i, j});
                        seen[i][j] = true;
                    }
                }
            }

            // 广度优先搜索
            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                int i = cell[0], j = cell[1];
                for (int d = 0; d < 4; ++d) {
                    int ni = i + dirs[d][0];
                    int nj = j + dirs[d][1];
                    if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) {
                        dist[ni][nj] = dist[i][j] + 1;
                        queue.offer(new int[]{ni, nj});
                        seen[ni][nj] = true;
                    }
                }
            }

            return dist;
        }
    }

    //官解：动态规划
    //建议看链接，从左上、右上、左下、右下分别向中间进行状态转移
    //链接：https://leetcode.cn/problems/01-matrix/solutions/202012/01ju-zhen-by-leetcode-solution/
    class Solution2 {
        static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        public int[][] updateMatrix(int[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            // 初始化动态规划的数组，所有的距离值都设置为一个很大的数
            int[][] dist = new int[m][n];
            for (int i = 0; i < m; ++i) {
                Arrays.fill(dist[i], Integer.MAX_VALUE / 2);
            }
            // 如果 (i, j) 的元素为 0，那么距离为 0
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (matrix[i][j] == 0) {
                        dist[i][j] = 0;
                    }
                }
            }
            // 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (i - 1 >= 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);
                    }
                    if (j - 1 >= 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
                    }
                }
            }
            // 只有 水平向左移动 和 竖直向下移动，注意动态规划的计算顺序
            for (int i = m - 1; i >= 0; --i) {
                for (int j = 0; j < n; ++j) {
                    if (i + 1 < m) {
                        dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
                    }
                    if (j - 1 >= 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
                    }
                }
            }
            // 只有 水平向右移动 和 竖直向上移动，注意动态规划的计算顺序
            for (int i = 0; i < m; ++i) {
                for (int j = n - 1; j >= 0; --j) {
                    if (i - 1 >= 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);
                    }
                    if (j + 1 < n) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
                    }
                }
            }
            // 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序
            for (int i = m - 1; i >= 0; --i) {
                for (int j = n - 1; j >= 0; --j) {
                    if (i + 1 < m) {
                        dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
                    }
                    if (j + 1 < n) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
                    }
                }
            }
            return dist;
        }
    }
}
